<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-2"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-3"></span><span class="hs-comment">-- Module      :  Control.Monad.State.Lazy</span><span>
</span><span id="line-4"></span><span class="hs-comment">-- Copyright   :  (c) Andy Gill 2001,</span><span>
</span><span id="line-5"></span><span class="hs-comment">--                (c) Oregon Graduate Institute of Science and Technology, 2001</span><span>
</span><span id="line-6"></span><span class="hs-comment">-- License     :  BSD-style (see the file LICENSE)</span><span>
</span><span id="line-7"></span><span class="hs-comment">--</span><span>
</span><span id="line-8"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- Stability   :  experimental</span><span>
</span><span id="line-10"></span><span class="hs-comment">-- Portability :  non-portable (multi-param classes, functional dependencies)</span><span>
</span><span id="line-11"></span><span class="hs-comment">--</span><span>
</span><span id="line-12"></span><span class="hs-comment">-- Lazy state monads.</span><span>
</span><span id="line-13"></span><span class="hs-comment">--</span><span>
</span><span id="line-14"></span><span class="hs-comment">--      This module is inspired by the paper</span><span>
</span><span id="line-15"></span><span class="hs-comment">--      /Functional Programming with Overloading and Higher-Order Polymorphism/,</span><span>
</span><span id="line-16"></span><span class="hs-comment">--        Mark P Jones (&lt;http://web.cecs.pdx.edu/~mpj/&gt;)</span><span>
</span><span id="line-17"></span><span class="hs-comment">--          Advanced School of Functional Programming, 1995.</span><span>
</span><span id="line-18"></span><span>
</span><span id="line-19"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-20"></span><span>
</span><span id="line-21"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Control.Monad.State.Lazy</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-22"></span><span>    </span><span class="annot"><span class="hs-comment">-- * MonadState class</span></span><span>
</span><span id="line-23"></span><span>    </span><span class="annot"><a href="Control.Monad.State.Class.html#MonadState"><span class="hs-identifier">MonadState</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-24"></span><span>    </span><span class="annot"><a href="Control.Monad.State.Class.html#modify"><span class="hs-identifier">modify</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-25"></span><span>    </span><span class="annot"><a href="Control.Monad.State.Class.html#modify%27"><span class="hs-identifier">modify'</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-26"></span><span>    </span><span class="annot"><a href="Control.Monad.State.Class.html#gets"><span class="hs-identifier">gets</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-27"></span><span>    </span><span class="annot"><span class="hs-comment">-- * The State monad</span></span><span>
</span><span id="line-28"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#State"><span class="hs-identifier">State</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-29"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#runState"><span class="hs-identifier">runState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-30"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#evalState"><span class="hs-identifier">evalState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-31"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#execState"><span class="hs-identifier">execState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-32"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#mapState"><span class="hs-identifier">mapState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-33"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#withState"><span class="hs-identifier">withState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-34"></span><span>    </span><span class="annot"><span class="hs-comment">-- * The StateT monad transformer</span></span><span>
</span><span id="line-35"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#StateT"><span class="hs-identifier">StateT</span></a></span><span class="hs-special">(</span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#StateT"><span class="hs-identifier">StateT</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-36"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#runStateT"><span class="hs-identifier">runStateT</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-37"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#evalStateT"><span class="hs-identifier">evalStateT</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-38"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#execStateT"><span class="hs-identifier">execStateT</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-39"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#mapStateT"><span class="hs-identifier">mapStateT</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-40"></span><span>    </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#withStateT"><span class="hs-identifier">withStateT</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-41"></span><span>    </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.html#"><span class="hs-identifier">Control.Monad</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-42"></span><span>    </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.Fix.html#"><span class="hs-identifier">Control.Monad.Fix</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-43"></span><span>    </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="Control.Monad.Trans.html"><span class="hs-identifier">Control.Monad.Trans</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-44"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Examples</span></span><span>
</span><span id="line-45"></span><span>    </span><span class="annot"><span class="hs-comment">-- $examples</span></span><span>
</span><span id="line-46"></span><span>  </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-47"></span><span>
</span><span id="line-48"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Control.Monad.State.Class.html"><span class="hs-identifier">Control.Monad.State.Class</span></a></span><span>
</span><span id="line-49"></span><span>
</span><span id="line-50"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Control.Monad.Trans.html"><span class="hs-identifier">Control.Monad.Trans</span></a></span><span>
</span><span id="line-51"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#"><span class="hs-identifier">Control.Monad.Trans.State.Lazy</span></a></span><span>
</span><span id="line-52"></span><span>        </span><span class="hs-special">(</span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#State"><span class="hs-identifier">State</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#runState"><span class="hs-identifier">runState</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#evalState"><span class="hs-identifier">evalState</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#execState"><span class="hs-identifier">execState</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#mapState"><span class="hs-identifier">mapState</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#withState"><span class="hs-identifier">withState</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-53"></span><span>         </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#StateT"><span class="hs-identifier">StateT</span></a></span><span class="hs-special">(</span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#StateT"><span class="hs-identifier">StateT</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#runStateT"><span class="hs-identifier">runStateT</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#evalStateT"><span class="hs-identifier">evalStateT</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#execStateT"><span class="hs-identifier">execStateT</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#mapStateT"><span class="hs-identifier">mapStateT</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../transformers/src/Control.Monad.Trans.State.Lazy.html#withStateT"><span class="hs-identifier">withStateT</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-54"></span><span>
</span><span id="line-55"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.html#"><span class="hs-identifier">Control.Monad</span></a></span><span>
</span><span id="line-56"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.Fix.html#"><span class="hs-identifier">Control.Monad.Fix</span></a></span><span>
</span><span id="line-57"></span><span>
</span><span id="line-58"></span><span class="hs-comment">-- ---------------------------------------------------------------------------</span><span>
</span><span id="line-59"></span><span class="hs-comment">-- $examples</span><span>
</span><span id="line-60"></span><span class="hs-comment">-- A function to increment a counter.  Taken from the paper</span><span>
</span><span id="line-61"></span><span class="hs-comment">-- /Generalising Monads to Arrows/, John</span><span>
</span><span id="line-62"></span><span class="hs-comment">-- Hughes (&lt;http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf&gt;), November 1998:</span><span>
</span><span id="line-63"></span><span class="hs-comment">--</span><span>
</span><span id="line-64"></span><span class="hs-comment">-- &gt; tick :: State Int Int</span><span>
</span><span id="line-65"></span><span class="hs-comment">-- &gt; tick = do n &lt;- get</span><span>
</span><span id="line-66"></span><span class="hs-comment">-- &gt;           put (n+1)</span><span>
</span><span id="line-67"></span><span class="hs-comment">-- &gt;           return n</span><span>
</span><span id="line-68"></span><span class="hs-comment">--</span><span>
</span><span id="line-69"></span><span class="hs-comment">-- Add one to the given number using the state monad:</span><span>
</span><span id="line-70"></span><span class="hs-comment">--</span><span>
</span><span id="line-71"></span><span class="hs-comment">-- &gt; plusOne :: Int -&gt; Int</span><span>
</span><span id="line-72"></span><span class="hs-comment">-- &gt; plusOne n = execState tick n</span><span>
</span><span id="line-73"></span><span class="hs-comment">--</span><span>
</span><span id="line-74"></span><span class="hs-comment">-- A contrived addition example. Works only with positive numbers:</span><span>
</span><span id="line-75"></span><span class="hs-comment">--</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- &gt; plus :: Int -&gt; Int -&gt; Int</span><span>
</span><span id="line-77"></span><span class="hs-comment">-- &gt; plus n x = execState (sequence $ replicate n tick) x</span><span>
</span><span id="line-78"></span><span class="hs-comment">--</span><span>
</span><span id="line-79"></span><span class="hs-comment">-- An example from /The Craft of Functional Programming/, Simon</span><span>
</span><span id="line-80"></span><span class="hs-comment">-- Thompson (&lt;http://www.cs.kent.ac.uk/people/staff/sjt/&gt;),</span><span>
</span><span id="line-81"></span><span class="hs-comment">-- Addison-Wesley 1999: \&quot;Given an arbitrary tree, transform it to a</span><span>
</span><span id="line-82"></span><span class="hs-comment">-- tree of integers in which the original elements are replaced by</span><span>
</span><span id="line-83"></span><span class="hs-comment">-- natural numbers, starting from 0.  The same element has to be</span><span>
</span><span id="line-84"></span><span class="hs-comment">-- replaced by the same number at every occurrence, and when we meet</span><span>
</span><span id="line-85"></span><span class="hs-comment">-- an as-yet-unvisited element we have to find a \'new\' number to match</span><span>
</span><span id="line-86"></span><span class="hs-comment">-- it with:\&quot;</span><span>
</span><span id="line-87"></span><span class="hs-comment">--</span><span>
</span><span id="line-88"></span><span class="hs-comment">-- &gt; data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)</span><span>
</span><span id="line-89"></span><span class="hs-comment">-- &gt; type Table a = [a]</span><span>
</span><span id="line-90"></span><span class="hs-comment">--</span><span>
</span><span id="line-91"></span><span class="hs-comment">-- &gt; numberTree :: Eq a =&gt; Tree a -&gt; State (Table a) (Tree Int)</span><span>
</span><span id="line-92"></span><span class="hs-comment">-- &gt; numberTree Nil = return Nil</span><span>
</span><span id="line-93"></span><span class="hs-comment">-- &gt; numberTree (Node x t1 t2)</span><span>
</span><span id="line-94"></span><span class="hs-comment">-- &gt;        =  do num &lt;- numberNode x</span><span>
</span><span id="line-95"></span><span class="hs-comment">-- &gt;              nt1 &lt;- numberTree t1</span><span>
</span><span id="line-96"></span><span class="hs-comment">-- &gt;              nt2 &lt;- numberTree t2</span><span>
</span><span id="line-97"></span><span class="hs-comment">-- &gt;              return (Node num nt1 nt2)</span><span>
</span><span id="line-98"></span><span class="hs-comment">-- &gt;     where</span><span>
</span><span id="line-99"></span><span class="hs-comment">-- &gt;     numberNode :: Eq a =&gt; a -&gt; State (Table a) Int</span><span>
</span><span id="line-100"></span><span class="hs-comment">-- &gt;     numberNode x</span><span>
</span><span id="line-101"></span><span class="hs-comment">-- &gt;        = do table &lt;- get</span><span>
</span><span id="line-102"></span><span class="hs-comment">-- &gt;             (newTable, newPos) &lt;- return (nNode x table)</span><span>
</span><span id="line-103"></span><span class="hs-comment">-- &gt;             put newTable</span><span>
</span><span id="line-104"></span><span class="hs-comment">-- &gt;             return newPos</span><span>
</span><span id="line-105"></span><span class="hs-comment">-- &gt;     nNode::  (Eq a) =&gt; a -&gt; Table a -&gt; (Table a, Int)</span><span>
</span><span id="line-106"></span><span class="hs-comment">-- &gt;     nNode x table</span><span>
</span><span id="line-107"></span><span class="hs-comment">-- &gt;        = case (findIndexInList (== x) table) of</span><span>
</span><span id="line-108"></span><span class="hs-comment">-- &gt;          Nothing -&gt; (table ++ [x], length table)</span><span>
</span><span id="line-109"></span><span class="hs-comment">-- &gt;          Just i  -&gt; (table, i)</span><span>
</span><span id="line-110"></span><span class="hs-comment">-- &gt;     findIndexInList :: (a -&gt; Bool) -&gt; [a] -&gt; Maybe Int</span><span>
</span><span id="line-111"></span><span class="hs-comment">-- &gt;     findIndexInList = findIndexInListHelp 0</span><span>
</span><span id="line-112"></span><span class="hs-comment">-- &gt;     findIndexInListHelp _ _ [] = Nothing</span><span>
</span><span id="line-113"></span><span class="hs-comment">-- &gt;     findIndexInListHelp count f (h:t)</span><span>
</span><span id="line-114"></span><span class="hs-comment">-- &gt;        = if (f h)</span><span>
</span><span id="line-115"></span><span class="hs-comment">-- &gt;          then Just count</span><span>
</span><span id="line-116"></span><span class="hs-comment">-- &gt;          else findIndexInListHelp (count+1) f t</span><span>
</span><span id="line-117"></span><span class="hs-comment">--</span><span>
</span><span id="line-118"></span><span class="hs-comment">-- numTree applies numberTree with an initial state:</span><span>
</span><span id="line-119"></span><span class="hs-comment">--</span><span>
</span><span id="line-120"></span><span class="hs-comment">-- &gt; numTree :: (Eq a) =&gt; Tree a -&gt; Tree Int</span><span>
</span><span id="line-121"></span><span class="hs-comment">-- &gt; numTree t = evalState (numberTree t) []</span><span>
</span><span id="line-122"></span><span class="hs-comment">--</span><span>
</span><span id="line-123"></span><span class="hs-comment">-- &gt; testTree = Node &quot;Zero&quot; (Node &quot;One&quot; (Node &quot;Two&quot; Nil Nil) (Node &quot;One&quot; (Node &quot;Zero&quot; Nil Nil) Nil)) Nil</span><span>
</span><span id="line-124"></span><span class="hs-comment">-- &gt; numTree testTree =&gt; Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil</span><span>
</span><span id="line-125"></span><span class="hs-comment">--</span><span>
</span><span id="line-126"></span><span class="hs-comment">-- sumTree is a little helper function that does not use the State monad:</span><span>
</span><span id="line-127"></span><span class="hs-comment">--</span><span>
</span><span id="line-128"></span><span class="hs-comment">-- &gt; sumTree :: (Num a) =&gt; Tree a -&gt; a</span><span>
</span><span id="line-129"></span><span class="hs-comment">-- &gt; sumTree Nil = 0</span><span>
</span><span id="line-130"></span><span class="hs-comment">-- &gt; sumTree (Node e t1 t2) = e + (sumTree t1) + (sumTree t2)</span><span>
</span><span id="line-131"></span></pre></body></html>